﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

     * */
    class Problem74 : IProblem
    {


        public string Calculate()
        {
            //taktika: popunit dictionary sa key je broj a value je rezultat operacije
            //nakraju nac najveci rekurzivno.


            int limit = 1000000;

            Dictionary<int, int> rezultati = new Dictionary<int, int>();
            

            for (int i = 1; i < limit; i++)
            {
                if (rezultati.ContainsKey(i))
                    continue;

                var digits = CommonFunctions.GetDigits(i);

                int sum = 0;
                foreach (int digit in digits)
                {
                    sum += (int)CommonFunctions.Factoriel(digit);
                }

                rezultati.Add(i, sum);

                while (true)
                {
                    int key = sum;
                    if (rezultati.ContainsKey(key))
                        break;

                    digits = CommonFunctions.GetDigits(key);

                    sum = 0;
                    foreach (int digit in digits)
                    {
                        sum += (int)CommonFunctions.Factoriel(digit);
                    }

                    rezultati.Add(key, sum);
                }
            }

            int count = 0;

            for (int i = 1; i < limit; i++)
            {
                int rezult = SequenceCount(i, rezultati, new List<int>());

                if (rezult == 60)
                {
                    Console.WriteLine("{0}",i);
                    count++;
                }
            }



            return count.ToString();
        }

        int SequenceCount(int key, Dictionary<int,int> rezultati, List<int> seenValues)
        {
            int sum = rezultati[key];

            if (seenValues.Contains(sum))
                return 1;

            seenValues.Add(sum);
            return 1 + SequenceCount(sum, rezultati, seenValues);
        }
    }
}
